package com.coder.algorithm.offer_2;

import java.util.Arrays;

/**
 * 0～n-1 中缺失的数字
 * <p>
 * 查找第一个下标小于数字的值
 *
 * @author yuhushuan
 * @date 2020/6/30 07:02
 */
public class _53_2_MissingNumber {
    private static int getMissingNumber(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return -1;
        }
        int start = 0;
        int end = numbers.length - 1;
        while (start <= end) {
            int middle = (start + end) >> 1;
            if (numbers[middle] != middle) {
                if (middle == 0 || numbers[middle - 1] == middle - 1) {
                    return middle;
                }
                end = middle - 1;
            } else {
                start = middle + 1;
            }

        }
        if (start == numbers.length) {
            return start;
        }
        return -1;
    }

    public static int missingNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            // 只有等于和大于
            if (nums[mid] != mid){// 在左区间
                if(nums[mid - 1] == mid - 1){
                    return mid;
                }
                right = mid - 1;
            }else {// 在右
                left = mid;
            }
        }
        return left+1;
    }

    public static void main(String[] args) {
        // 功能测试
        // 缺失的数字位于数组的开始、中间或者末尾
        print(new int[] {0,1,3});
//        print(new int[]{1, 2, 3, 4, 5, 6});
//        print(new int[]{0, 1, 2, 3, 5, 6});
//        print(new int[]{0, 1, 2, 3, 4, 5});

        //边界值测试
//        print(new int[]{0});

        print(null);
    }

    private static void print(int[] numbers) {
        System.out.println("数组：" + Arrays.toString(numbers));
        System.out.println("缺失的数字为：" + missingNumber(numbers));
        System.out.println();
    }
}
